#include <stdio.h>
#include <stdlib.h>

typedef char ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode
{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

BinTree CreatBinTree(); /* 实现细节忽略 */
void InorderTraversal(BinTree BT);
void PreorderTraversal(BinTree BT);
void PostorderTraversal(BinTree BT);
void LevelorderTraversal(BinTree BT);

int main()
{
    BinTree BT = CreatBinTree();
    printf("Inorder:");
    InorderTraversal(BT);
    printf("\n");
    printf("Preorder:");
    PreorderTraversal(BT);
    printf("\n");
    printf("Postorder:");
    PostorderTraversal(BT);
    printf("\n");
    printf("Levelorder:");
    LevelorderTraversal(BT);
    printf("\n");
    return 0;
}
/* 你的代码将被嵌在这里 */

void InorderTraversal(BinTree BT)
{
    BinTree stack[100];
    int top = -1; // 统一初始化为 -1 表示栈空
    BinTree cur = BT;
    while (cur != NULL || top >= 0)
    {
        if (cur != NULL)
        {
            stack[++top] = cur; // 入栈操作修改为先自增再赋值
            cur = cur->Left;
        }
        else
        {
            cur = stack[top--]; // 出栈操作先取值再自减
            printf(" %c", cur->Data);
            cur = cur->Right;
        }
    }
}

void PreorderTraversal(BinTree BT)
{
    BinTree stack[100];
    int top = -1; // 初始化为 -1
    if (BT != NULL)
    {
        stack[++top] = BT; // 入栈操作先自增再赋值
        while (top >= 0)
        {
            BinTree cur = stack[top--]; // 出栈操作先取值再自减
            printf(" %c", cur->Data);
            if (cur->Right != NULL)
                stack[++top] = cur->Right; // 入栈操作先自增再赋值
            if (cur->Left != NULL)
                stack[++top] = cur->Left; // 入栈操作先自增再赋值
        }
    }
}

void PostorderTraversal(BinTree BT)
{
    BinTree stack[100];
    int top = -1;
    BinTree lastVisited = NULL;
    while (BT || top >= 0)
    {
        while (BT)
        {
            stack[++top] = BT;
            BT = BT->Left;
        }
        BT = stack[top];
        // 如果右子树为空或者右子树已经被访问过
        if (BT->Right == NULL || BT->Right == lastVisited)
        {
            printf(" %c", BT->Data);
            lastVisited = BT;
            top--;
            BT = NULL;
        }
        else
        {
            BT = BT->Right;
        }
    }
}

void LevelorderTraversal(BinTree BT)
{
    BinTree queue[100];
    int front = 0;
    int rear = 0;
    if (BT != NULL)
    {
        queue[rear++] = BT;
        while (front < rear)
        {
            BinTree cur = queue[front++];
            printf(" %c", cur->Data);
            if (cur->Left != NULL)
                queue[rear++] = cur->Left;
            if (cur->Right != NULL)
                queue[rear++] = cur->Right;
        }
    }
}


